#include<bits/stdc++.h>
const int INF = 0x3f3f3f3f;
using namespace std;
int n, m;
int bit[12] = { 0,1,3,9,27,81,243,729,2187,6561,19683,59049 };
//三进制每一位的权值。与二进制的0, 1, 2, 4, 8...对照理解

int tri[60000][11];
int dp[11][60000];
int graph[11][11];                   //存图

void make_trb() {                     //初始化，求所有可能的路径
    for (int i = 0;i < 59050;++i) {       //共3^10 = 59050种路径状态
        int t = i;
        for (int j = 1; j <= 10; ++j) { tri[i][j] = t % 3;  t /= 3; }
    }
}

int comp_dp() {
    int ans = INF;
    memset(dp, INF, sizeof(dp));
    for (int j = 0;j <= n;j++)
        dp[j][bit[j]] = 0;            //初始化：从第j个城市出发，只访问j，费用为0
    for (int i = 0;i < bit[n + 1];i++) {    //遍历所有路径，每个i是一个路径
        int flag = 1;                 //所有的城市都遍历过1次以上
        for (int j = 1;j <= n;j++) {      //遍历城市，以j为起点
            if (tri[i][j] == 0) {     //是否有一个城市访问次数是0
                flag = 0;             //还没有经过所有点
                continue;
            }
            for (int k = 1; k <= n; k++) {    //遍历路径i-j的所有城市
                int l = i - bit[j];         //l:从路径i中去掉第j个城市
                dp[j][i] = min(dp[j][i], dp[k][l] + graph[k][j]);
            }
        }
        if (flag)                        //找最小费用
            for (int j = 1; j <= n; j++)
                ans = min(ans, dp[j][i]);  //路径i上，最小的总费用
    }
    return ans;
}

int main() {
    make_trb();
    while (cin >> n >> m) {
        memset(graph, INF, sizeof(graph));
        while (m--) {
            int a, b, c; cin >> a >> b >> c;
            if (c < graph[a][b]) graph[a][b] = graph[b][a] = c;
        }
        int ans = comp_dp();
        if (ans == INF) cout << "-1" << endl;
        else         cout << ans << endl;
    }
    return 0;
}
